%%%-------------------------------------------------------------------
%%% File    : p48.erl
%%% Author  :  Plamen Dragozov <plamen@dragozov.com>
%%% Description : 
%%% The series, 1^(1) + 2^(2) + 3^(3) + ... + 10^(10) = 10405071317.
%%% Find the last ten digits of the series, 
%%% 1^(1) + 2^(2) + 3^(3) + ... + 1000^(1000)
%%%
%%% Created :  4 Jan 2009
%%%-------------------------------------------------------------------
-module(p48).

%% API
-compile(export_all).

%%====================================================================
%% API
%%--------------------------------------------------------------------
%% Function: solution(N, Digits) > X.
%% Description: Returns the last Digits digits of the sum 1 + 2^2+....+N^N
%%--------------------------------------------------------------------
solution(N, Digits) ->
    for(N, pow(10, Digits), 0).

for(1, Pow10, Acc) -> (Acc + 1) rem Pow10;
for(X, Pow10, Acc) ->
    for(X - 1, Pow10, Acc + (pow(X, X) rem Pow10)).
%%====================================================================
%% Internal functions
%%====================================================================
%Fast integer exponentiation
pow(_, 0) -> 1;
pow(X, 1) -> X;
pow(X, N) ->
    case N rem 2 of 
        0 ->
            R = pow(X, N div 2),
            R*R;
        _ -> X * pow(X, N - 1)
    end.
